package com.cuz.daileetcode;

/***
 * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方
 * 组成的新数组，要求也按 非递减顺序 排序。
 *
 * 示例 1： 输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，
 * 数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]
 *
 * 示例 2： 输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]
 *
 * https://leetcode-cn.com/problems/squares-of-a-sorted-array/
 */
public class Day20 {
    /***
     * 注意
     * 非递减顺序 排序的整数数组 nums，
     * 也就意味着大于0的部分相对顺序不需要改变
     * 小于0的部分平方存在大于整数平方的情况
     * 我们使用双指针
     * 其实排序的依据就是整个数到数轴0的举例
     * -4 1 2 3
     * 16 1 4 9
     *
     * @param nums
     * @return
     */
    public static int[] sortedSquares(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        int left = 0;
        int right = nums.length - 1;
        int[] res = new int[nums.length];
        int indexOfRes = nums.length - 1;
        while (left < right) {
            int leftSeq = nums[left] * nums[left];
            int rightReq = nums[right] * nums[right];
            //负数平方大于 正数平方
            if (leftSeq > rightReq) {
                res[indexOfRes] = rightReq;
                left++;
            }else {
                res[indexOfRes] = leftSeq;
                right--;
            }
            indexOfRes--;
        }
        return res;
    }
}
